package BinarySearch;

import java.util.HashMap;
import java.util.Objects;

/**
 * @Author Fizz Pu
 * @Date 2020/8/22 下午4:44
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class Demo {

    public static void main(String[] args) {
        // 测试SearchFirstGreaterOrEqualTarget
        System.out.println("------测试SearchFirstGreaterOrEqualTarget---------------");
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1},0));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1},1));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1},2));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2},1));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2},2));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2},3));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2,3,4,5},3));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2,3,4,5},0));
        System.out.println(SearchFirstGreaterOrEqualTarget(new int[]{1,2,3,4,5},9));

        // 测试SearchLastLessTarget
        System.out.println("------测试SearchLastLessTarget---------------");
        System.out.println(SearchLastLessTarget(new int[]{1},0));
        System.out.println(SearchLastLessTarget(new int[]{1},1));
        System.out.println(SearchLastLessTarget(new int[]{1},2));
        System.out.println(SearchLastLessTarget(new int[]{1,2},1));
        System.out.println(SearchLastLessTarget(new int[]{1,2},2));
        System.out.println(SearchLastLessTarget(new int[]{1,2},3));
        System.out.println(SearchLastLessTarget(new int[]{1,2,3,4},3));
        System.out.println(SearchLastLessTarget(new int[]{1,2,3,4},5));
        System.out.println(SearchLastLessTarget(new int[]{1,2,3,4},0));

        // 测试SearchFirstGreaterTarget
        System.out.println("------测试SearchFirstGreaterTarget---------------");
        System.out.println(SearchFirstGreaterTarget(new int[]{1},0));
        System.out.println(SearchFirstGreaterTarget(new int[]{1},1));
        System.out.println(SearchFirstGreaterTarget(new int[]{1},2));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2},1));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2},2));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2},3));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2,3,4},3));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2,3,4},5));
        System.out.println(SearchFirstGreaterTarget(new int[]{1,2,3,4},0));

        // 测试SearchLastLessOrEqualTarget
        System.out.println("------测试SearchLastLessOrEqualTarget---------------");
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1},0));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1},1));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1},2));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2},1));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2},2));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2},3));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2,3},3));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2,3},0));
        System.out.println(SearchLastLessOrEqualTarget(new int[]{1,2,4},5));

        HashMap<Integer, Integer> res = new HashMap<>();
        System.out.println(res.put(1,2));
        System.out.println(res.remove(3));
        res.put(1,null);
        System.out.println(res.get(1));
        Objects.hash(1,2,"fdsf");
    }




    /**
     * 子有序表中搜索target对应的下标，若不存在，则返回-1;
     * @param arr
     * @param target
     * @return
     */

    public static int SerachSpeValue(int[] arr, int target){
        int low = 0, high = arr.length - 1, mid;
        while(low <= high){
            mid = low + (high - low) / 2; // 防止溢出
            if (arr[mid] == target)return mid;
            else if (arr[mid] < target)low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    /**
     * 搜索第一个大于等于target的值
     * @param arr 升序数组
     * @param target
     * @return
     */
    public static int SearchFirstGreaterOrEqualTarget(int[] arr, int target){
        int low = 0, length = arr.length, high = length, mid; // 注意high是length ，不是length - 1
        while(low < high){ // <= 可能会造成死循环
            mid = low + (high - low) / 2;
            if (arr[mid] < target)low = mid + 1;   // 大于等于的数一定在mid后面
            else high = mid;                  // mid对应的数字有可能是第一个大于等于target的，也有可能是不是，需要缩小。
        }
        if (high == length)return -1; // 不存在的话,high = length
        return high;   // high对应第一个大于等于的数字
    }

    /**
     * 搜索第一个小于的数字，就是搜索第一个大于等于target的值的变体，修改下搜索不到的条件
     * if (arr[0] >= target)return -1;
     * 退出后返回high - 1;
     */

    public static int SearchLastLessTarget(int[] arr, int target){
        int low = 0, length = arr.length, high = length, mid;
        while(low < high){ // <= 会造成死循环
            mid = low + (high - low) / 2;
            if (arr[mid] < target)low = mid + 1;   // 大于等于的数一定在mid后面
            else high = mid;                  // mid对应的数字有可能是第一个大于等于target的，也有可能是不是，需要缩小。
        }
        if (high == 0)return high - 1; // 不存在的话,high = 0 ,则返回-1
        return high - 1;   // high对应第一个大于等于的数字,没有返回length,减一后必然小于target。
    }

    /**
     * 搜索第一个大于target的值的下标，不存在则返回-1
     * @param arr 升序数组
     * @param target
     * @return
     */
    public static int SearchFirstGreaterTarget(int[] arr, int target){
        int low = 0, length = arr.length, high = length, mid;
        while(low < high){ // <= 会造成死循环
            mid = low + (high - low) / 2;
            if (arr[mid] <= target)low = mid + 1;   // 大于target的数一定在mid后面
            else high = mid;                  // mid对应的数字有可能是第一个大于target的，也有可能是不是，需要缩小。
        }
        if (high == length)return -1;
        return high;
    }

    /**
     * 搜索第一个小于等于target的数字，就是搜索第一个大于target的值的变体，修改下搜索不到的条件
     * if (arr[0] > target)return -1;
     * 退出后返回high - 1;
     */
    public static int SearchLastLessOrEqualTarget(int[] arr, int target){
        int low = 0, length = arr.length, high = length, mid;
        while(low < high){ // <= 会造成死循环
            mid = low + (high - low) / 2;
            if (arr[mid] <= target)low = mid + 1;   // 大于target的数一定在mid后面
            else high = mid;                  // mid对应的数字有可能是第一个大于target的，也有可能是不是，需要缩小。
        }
        // if (high == 0)return high - 1; 和下一句合并
        return high - 1;
    }

}
